package com.wfm.leetcode.editor.cn;

import com.wfm.common.TreeNode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * 就是二叉树的正常层序遍历
 *      3
 *     9  20
 *       15  7
 * 输出
 *  【3,9,20,15,7】
 */
public class P剑指Offer32I从上到下打印二叉树{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null){
            return new int[0];
        }
        List<Integer> res = new ArrayList<>();

        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            int curSize = q.size();
            for (int i = 0; i < curSize; i++) {
                TreeNode poll = q.poll();
                res.add(poll.val);
                if(poll.left!=null) q.offer(poll.left);
                if(poll.right!=null) q.offer(poll.right);
            }
        }

//        执行耗时:3 ms,击败了18.09% 的Java用户
//        内存消耗:40.3 MB,击败了84.97% 的Java用户
//        return res.stream().mapToInt(Integer::valueOf).toArray();

//        执行耗时:1 ms,击败了96.64% 的Java用户
//        内存消耗:40.1 MB,击败了94.16% 的Java用户
        int[] r = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            r[i]=res.get(i);
        }
        return r;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new P剑指Offer32I从上到下打印二叉树().new Solution();
    }
}